
export class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}

/**
 * https://leetcode-cn.com/problems/insertion-sort-list/submissions/
 * 对链表进行插入排序
 * @param head 
 */
const insertionSortList = (head: ListNode | null): ListNode | null => {
    // 头节点或者头节点的下一个为空
    if (head == null || head.next === null) return head


    // 1. 使用虚拟头节点
    const dummyHead = new ListNode(0);
    dummyHead.next = head;


    // 2. 从第二项开始进行插入排序
    let sorted = head,
        current = head.next;

    // 3. 从current开始, 直到current变为空
    while (current !== null) {
        if (current.val >= sorted.val) {
            //  当前值比上一个大, 说明不用进行排序
            sorted = sorted.next!;
        } else {
            // 当前值比上一个小
            // 1. 从头开始找到第一个比current大的值, 同时找到该值的前一个
            let prev = dummyHead;
            while (prev.next!.val <= current.val) {
                prev = prev.next!;
            }
            sorted.next = current.next;
            current.next = prev.next
            prev.next = current;
        }

        // 让current指向已经排序的下一个
        current = sorted.next!;
    }

    return dummyHead.next;
};


const insertionSortList2 = (head: ListNode | null): ListNode | null => {
    // 头节点或者头节点的下一个为空
    if (head == null || head.next === null) return head
    let root = head;


    let oldRoot: ListNode;

    // 一直遍历, 直到head.next为空
    let next = head.next;
    let oldPre = head;
    // -1 5 3 4 0
    while (next !== null) {
        const n = next.next

        // 从头找, 需要交换
        // 保存当前的头
        oldRoot = root;
        let prev = root;

        while (root !== null && root !== next) {
            // 当前的值大于要比较的值
            if (root.val > next.val) {

                if (prev == root) {
                    // 是首节点
                    oldRoot = next;
                    oldPre.next = next.next;
                    next.next = root;

                } else {
                    // 不是首节点   
                    prev.next = next;
                    oldPre.next = next.next;
                    next.next = root;
                }
                break;
            } else {
                prev = root;
                root = root.next!;
            }
        }
        // 恢复root
        while (root.next) {
            if (root.val < root.next.val) root = root.next
            else break;
        }

        oldPre = root;
        root = oldRoot;
        // debugger
        next = n!;
    }

    return root;
};


const head = new ListNode(-1)
head.next = new ListNode(5)
head.next.next = new ListNode(3)
head.next.next.next = new ListNode(4)
head.next.next.next.next = new ListNode(0)
// const head = new ListNode(4)
// head.next = new ListNode(2)
// head.next.next = new ListNode(1)
// head.next.next.next = new ListNode(3)

// debugger
let r3 = insertionSortList(head);
console.log(r3)
// while (r3 !== null) {
//     console.log(r3.val)
//     r3 = r3.next;
// }
